#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include "utils.h"
using namespace std;

class Solution {
public:
    void pathSum(TreeNode *root, list<int> &l, int sum, vector<vector<int> > &v) {
        if (root == NULL) return;
        l.push_back(root->val);
        if (root->left == NULL && root->right == NULL ) {
            if (root->val == sum) {
                vector<int> sub_v;
                for (list<int>::iterator it = l.begin(); it!=l.end(); it++) {
                    sub_v.push_back(*it);
                }
                v.push_back(sub_v);
            }
            return ;
        }

        if (root->left != NULL) {
            pathSum(root->left, l, sum-root->val, v);
            l.pop_back();
        }
        if (root->right != NULL) {
            pathSum(root->right, l, sum-root->val, v);
            l.pop_back();
        }
    }

    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > v;
        list<int> l;
        if (root!=NULL) { pathSum(root, l, sum, v); }
        return v;
    }
};

int main(int argc, char *argv[])
{
    int a[] = {5, 4, 8, 11, -1, 13, 4, 7, 2, -1, -1, 5, 1};
    vector<int> v(a, a+sizeof(a)/sizeof(int));
    TreeNode *root = build_binary_tree(v);
    print_vector(levelOrder(root));

    Solution ss;
    int sum = 22;
    print_vector(ss.pathSum(root, sum));

    return 0;
}
